package sword.offer;

/**
 * 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
 * 例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
 * <p>
 * 链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
 *
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class TwentyTwo {
    /**
     * 这道题巧妙利用双指针，时间复杂度为O(n)
     * 第一个指针在第二个指针的前面，且距离k个元素 这样当第一个指针落在最后一个元素的时候 第二个指针就会停在倒数第k
     * */
    class Solution {
        public ListNode getKthFromEnd(ListNode head, int k) {
            ListNode res = head;
            // 往后先走k步
            for (int i = 0; i < k; i++) {
                head = head.next;
            }
            while(head != null){
                res = res.next;
                head = head.next;
            }
            return res;
        }
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
